package 数组题目.数组排序;

import java.util.Arrays;

//排序按矩阵对角线排序
//https://leetcode.cn/problems/sort-the-matrix-diagonally/
class 按矩阵对角线排序 {
    public int[][] diagonalSort(int[][] mat) {
        int maxCol = mat.length;
        int maxRow = mat[0].length;
        if (maxCol == 1 || maxRow == 1) return mat;
        //思路：从左下角开始遍历
        // 先让 层数从 0 -> mat.length
        // 再让 行数从 0 -> mat[0].length
        //这样子就遍历完全部对角线
        int n = mat.length - 1;
        // 排序下三角形区域
        while (n >= 0) {
            // 排序对角线的第几个
            for (int i = 0; i < mat.length - n; i++) {
                int next = n + i; // 对应排序开始的层数
                // 采用冒泡排序
                for (int col = next, row = i; col < maxCol && row < maxRow; col++, row++) {
                    if (mat[next][i] > mat[col][row]) {
                        int temp = mat[next][i];
                        mat[next][i] = mat[col][row];
                        mat[col][row] = temp;
                    }
                }
            }
            n--;
        }
        // 排序剩余区域
        int m = 1;
        while (m < maxRow) {
            // 排序对角线的第几个
            for (int i = 0; i < maxRow - m; i++) {
                int next = m + i; // 对应排序开始的列数
                // 采用冒泡排序
                for (int row = next, col = i; col < maxCol && row < maxRow; col++, row++) {
                    if (mat[i][next] > mat[col][row]) {
                        int temp = mat[i][next];
                        mat[i][next] = mat[col][row];
                        mat[col][row] = temp;
                    }
                }
            }
            m++;
        }
        return mat;
    }

    public static void main(String[] args) {
        按矩阵对角线排序 按矩阵对角线排序 = new 按矩阵对角线排序();
        int[][] mat = new int[][]{{75, 21, 13, 24, 8}, {24, 100, 40, 49, 62}};
        int[][] res = 按矩阵对角线排序.diagonalSort(mat);
        System.out.println(Arrays.deepToString(res));
    }
}
